/**
 * 
 */
package leetCode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author zhong
 *
 */
public class ChalkboardXORGame {
	public boolean xorGame(int[] nums) {
		// Arrays.sort(nums);
		return willWin(nums, new boolean[nums.length]);
	}

	private boolean willWin(int[] nums, boolean[] isEmpty) {
		int cnt = 0;
		int x = 0;
		for (int i = 0; i < nums.length; i++) {
			if (!isEmpty[i]) {
				cnt++;
				x ^= nums[i];
			}
		}
		if (x == 0) {
			return true;
		}
		if (cnt == 1) {
			return false;
		}
		Set<Integer> added = new HashSet<>();
		for (int i = 0; i < nums.length; i++) {
			if (!isEmpty[i] && nums[i] != x && added.add(nums[i])) {// 1.没有被擦除，2.不直接使得擦出后异或结果为0 3.之前没有加入过该值
				isEmpty[i] = true;
				if (!willWin(nums, isEmpty)) {// 只要有方法使得对方输，则可以设置为赢
					// isEmpty[i] = false;
					return true;
				}
				isEmpty[i] = false;
			}
		}
		return false;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] nums = { 7, 8, 6, 10, 14, 15, 16, 6, 4, 0, 4, 9, 3, 3, 8, 10, 5, 5, 3, 10 };
		// { 1, 1, 2, 3 };
		// {7,8,6,10,14,15,16,6,4,0,4,9,3,3,8,10,5,5,3,10}
		System.out.println(new ChalkboardXORGame().xorGame(nums));
	}

}
